Modern processors typically provide hardware support for virtual memory systems by performing virtual to physical address mappings in hardware. Both the virtual and physical memory address spaces can be contemplated as a collection of "pages" of a predetermined size, often four kilobytes (4 kB). A set of mappings between virtual and physical memory pages which define the current virtual address space is stored in a data structure commonly called a "page table". Typically, entries in the page table further include access protection information and other control information such as software maintained flags and reference counts. The page table information is accessed quite frequently since it is used on substantially each memory reference. Unfortunately, the page table is typically too large to store on-chip within a central processing unit (CPU). Instead, a translation lookaside buffer (TLB) is used to cache the most recently used page table entries with the CPU.
When a reference is made to a virtual memory address, most mappings can be immediately performed via a TLB lookup. If a desired entry is not found in the TLB (often referred as a "TLB miss"), a page table lookup is performed to fetch the required information. If the desired entry is further not located within a page table in primary memory (eg. semiconductor random access memory--RAM), a "page Fault" occurs and an appropriate physical memory page is found, for example on a secondary memory system such as a hard disk, and loaded into primary memory for subsequent direct access by the CPU. An appropriate page table entry for the physical memory page is then loaded into the page table thus making the desired entry available. In a multiprocessor system, where a plurality of processors can access a page table, a first processor can be attempting a page table update while a page table lookup from a second processor is in progress, which can result in a possible conflict. A mechanism is normally required or set in place to resolve this possible conflict.
To directly index a page table utilizing a portion of the virtual memory address requires that the page table be as large as the indexing that is possible from the virtual page number. For example, if the twenty most significant bits of the virtual memory address are utilized as the virtual page number, an indexing of up to 1 Meg. of pages (1,048,576 pages) is possible. A page table accommodating more than a million virtual pages occupies a significant portion of memory. On a computer system running several applications, each having an associated page table, the total number of page tables could thus occupy a substantial part of the physical memory. It is therefore desirable to reduce the size of the page table.
Several techniques are available to reduce the page table size. One such technique is to limit the size of the page table to a predetermined size and if a request for an entry indexed by a virtual page number is outside the limits of the page table, an entry is made to the page table to account for the request. In this manner the page table is increased (or grown) to a required size, rather than being created to a size as large as that addressable by the virtual page number.
Another technique of reducing the page table size is to apply a "hashing function" to the virtual page number in such a manner as to reduce a virtual page number value to a smaller hashed index value which is used to index a smaller page table structure that addresses those physical memory pages in main memory.
The smaller page table resulting from the technique of applying a hashing function is often referred to as an "inverted page table" or "hashed page table". A hashing function typically maps substantially all virtual page numbers in a virtual memory system to a smaller subset of values herein referred to as hashed index values.
Consequently, applying a hashing function to a virtual page number can result in more than one virtual page number corresponding with a hashed index value. As a result a "hash collision" occurs, on an inverted page table lookup, when a current virtual address is hashed (ie. hash function applied) to obtain a hashed index value which is used to index an inverted page table entry having a virtual address, and the virtual address does not correspond to the current virtual address.
Similarly, when adding a new entry to an inverted page table, a "hash collision" occurs when a current virtual address is hashed to obtain a hashed index value which indexes an inverted page table entry currently occupied by a valid entry (ie. an entry having a valid flag set as described hereinafter).
A conflict arises if system software attempts to update the page table at the same time that a processor (or co-processor) of the system attempts a page table lookup resulting from a TLB miss. One solution to this conflict is to prevent page table lookups by locking out page table lookups while the table is being updated. However, locking the page table in this manner has adverse performance implications.
The above mentioned conflict is common to both multiprocessor systems (since multiple processors may be doing a page table lookup at any time) and uniprocessor systems (since the page table lookup is such a fundamental operation that a lookup may occur even while executing the privileged operating system code which updates the page table itself).
For example, a system using a graphics co-processor is inherently a multiprocessor system. Further, requiring synchronisation of the multiprocessors in relation to page table accesses is undesirable because the graphics co-processor may need to be halted, in the synchronisation process, effectively slowing down the image processing.